class Zcsh {
    public int[] countBits(int num) {
        if (num == 0) {
            return new int[]{0};
        }
        int[] result = new int[num + 1];
        result[1] = 1;
        int preFlagNumber = 1;
        for (int i = 2; i < result.length; i++) {
            if (i - preFlagNumber == preFlagNumber) {
                result[i] = 1;
                preFlagNumber = i;
            } else {
                result[i] = result[preFlagNumber] + result[i - preFlagNumber];
            }
        }

        return result;
    }
}